package leetcode.每日一题;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/31 10:44
 * @description :https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/
 */
public class 二叉树的垂序遍历 {
    @Test
    public void test() {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(3, new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        solution.verticalTraversal(root);
    }

    class Solution {
        public List<List<Integer>> verticalTraversal(TreeNode root) {
            if (root == null) return null;
            ArrayList<int[]> nodes = new ArrayList<>();
            dfs(root, 0, 0, nodes);
            Collections.sort(nodes, ((o1, o2) -> {
                if (o1[1] != o2[1]) return o1[1] - o2[1];
                if (o1[0] != o2[0]) return o1[0] - o2[0];
                return o1[2] - o1[2];
            }));
            for (int[] node : nodes) {
                System.out.println(Arrays.toString(node));
            }
            List<List<Integer>> ans = new ArrayList<>();
            List<Integer> sub = new ArrayList<>();
            int pre = nodes.get(0)[1];
            for (int[] node : nodes) {
                if (node[1] == pre) {
                    sub.add(node[2]);
                } else {
                    ans.add(sub);
                    sub = new ArrayList<>();
                    sub.add(node[2]);
                }
                pre = node[1];
            }
            if (sub.size() > 0) ans.add(sub);
            for (List<Integer> an : ans) {
                System.out.println(an);
            }
            return null;
        }

        private void dfs(TreeNode node, int row, int col, ArrayList<int[]> nodes) {
            if (node == null) return;
            nodes.add(new int[]{row, col, node.val});
            dfs(node.left, row + 1, col - 1, nodes);
            dfs(node.right, row + 1, col + 1, nodes);
        }
    }
}
